W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Biolodzy zajmujący się genetyką porównawczą poszukują sekwencji genów zachowanych w pewnym zbiorze gatunków.
Niech zbiór liczb oznacza geny - każdej liczbie odpowiada jeden gen.
Każdy z gatunków określony jest permutacją liczb , która oznacza uporządkowanie jego genów.
Ciąg genów jest zachowaną sekwencją genów w zbiorze gatunków, jeśli jest on podciągiem (niekoniecznie spójnym)
uporządkowania genów każdego z tych gatunków.
Zadanie
Napisz program, który:
wczyta ze standardowego wejścia opis sekwencji genów,
wyznaczy długość najdłuższej zachowanej sekwencji,
zapisze odpowiedź na standardowe wyjście.
Wejście
W pierwszej linii standardowego wejścia znajdują się dwie liczby całkowite i oddzielone pojedynczym odstępem,
przy czym oraz . Liczba oznacza liczbę genów, a liczbę gatunków.
Każda z następnych linii zawiera genom kolejnego gatunku zapisany jako permutacja liczb pooddzielanych pojedynczymi odstępami.
Wyjście
Na wyjściu powinna zostać wypisana dokładnie jedna liczba całkowita równa długości najdłuższej zachowanej sekwencji genów.
Przykład
Dla danych wejściowych:
5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4
poprawną odpowiedzią jest:
3
Wyjaśnienie
Podciągi:
są zachowanymi sekwencjami genów wśród tych 3 gatunków. Najdłuższą zachowaną sekwencją genów
tych 3 gatunków jest .